    წონიანი გრაფები (Weighted Graphs).
უმოკლესი გზების პოვნა ერთი წვეროდან
   (Single Source Shortest Paths), ზოგადი
 მიდგომა. ამოცანები რომლებიც იხსნება
             DFS-ით და BFS ით.
              მარიამ გობრონიძე
განმარტება
G=(V, E) გრაფი წარმოადგენს წვეროების V სიმრავლის და
წიბოების E სიმრავლის წყვილს. ყოველი წიბო წარმოადგენს
წვეროების დალაგებულ ან დაულაგებელ წყვილს. წიბოები
მიმართულია, თუ E სიმრავლის ელემენტები დალაგებული
წყვილებია, წინააღმდეგ შემთხვევაში - არამიმართული.
გრაფს ეწოდება წონიანი, თუ ყოველ წიბოსთან ასოცირებულია
რიცხვი - ამ წიბოს წონა. წინააღმდეგ შემთხვევაში გრაფს უწონო
ეწოდება.
წონიანი გრაფის გამოყენებები

2D თამაშები: მაქსიმალური ჯამის ან ოპტიმალური ბილიკის პოვნა.
განფენილი ხეები (Spanning Trees): მინიმალური წონის მქონე გზის
გამოთვლა, რომელიც მოივლის გრაფის ყველა წვეროს.
შეზღუდვების გრაფები (Constraint Graphs): დაგეგმვა, პროდუქტების
დიზაინი, რესურსების განაწილება.
დამოკიდებულებების გრაფები (Dependency Graphs): პრიორიტეტებისა და
თანმიმდევრობის მართვა პროექტებში.
კომპილატორები: მონაცემთა ნაკადების ანალიზი და მოთხოვნების
ოპტიმიზაცია.
ხელოვნური ინტელექტი: გადაწყვეტილების მიღების პროცესები თამაშებში.
სურათების დამუშავება: სეგმენტაცია პიქსელთა მსგავსების მიხედვით.
ბუნებრივი ენის დამუშავება: ტექსტების კლასიფიკაცია სიტყვების მსგავსებით.
წონიანი გრაფების რეალური
გამოყენებები
● ტრანსპორტის ქსელები: ოპტიმალური მარშრუტების პოვნა (Uber, Google
  Maps).
● ბმული წონიანი გრაფები: ვებ-გვერდების სანდოობის შეფასება.
● ეპიდემიოლოგია: დაავადებების გადაცემის მოდელირება.
● კვანტური ველის თეორია: მდგომარეობებსა და გადასვლებს შორის
  ანალიზი.
● სოციალური ქსელები: პირდაპირი და არაპირდაპირი კავშირების
  შეფასება.
წონიანი გრაფების უპირატესობები
რეალური სამყაროს უკეთესი წარმოდგენა.

უფრო ზუსტი ბილიკის პოვნა.

ეფექტური ალგორითმები (მაგ.: Dijkstra-ს ალგორითმი).

ანალიზის მოქნილობა.

უნდობლობის მოდელირების შესაძლებლობა.
რეალური სამყაროსთან უკეთესი
შესაბამისობა
წონიანი გრაფები უფრო ზუსტად ასახავენ რეალურ ამოცანებს.
მაგალითად, საგზაო ქსელში გზებს შესაძლოა ჰქონდეთ
განსხვავებული სიჩქარის ლიმიტები ან ზოლების
განსხვავებული რაოდენობა — ეს განსხვავებები შეიძლება
წონების საშუალებით წარმოვადგინოთ.
უფრო ზუსტი მარშრუტის ძიება
წონიან გრაფებში ორი წვეროს შორის ყველაზე მოკლე
მარშრუტის მოძიება ითვალისწინებს წონებს, რაც შედეგს უფრო
ზუსტს ხდის.
ეს განსაკუთრებით მნიშვნელოვანია ისეთ სფეროებში,
როგორიცაა ლოჯისტიკა ან სატრანსპორტო დაგეგმარება.
უფრო ეფექტური ალგორითმები
ბევრი გრაფის ალგორითმი წონიან გრაფებზე უფრო
ეფექტურად მუშაობს. მაგალითად, დეიქსტრას ალგორითმი
Shortest Path-ის (მოკლე მარშრუტის) გამოსათვლელად წონებს
იყენებს, ძიების პროცესის ოპტიმალურობისათვის.
ანალიზის მეტი მოქნილობა
წონიანი გრაფები იძლევა კავშირების დეტალურად ანალიზის
საშუალებას. მაგალითად, შესაძლებელია გამოითვალოს
წონების საშუალო მნიშვნელობა ან გამოვლინდეს წერტილები,
რომლებსაც არაბუნებრივად მაღალი ან დაბალი წონა აქვთ.
ეს ინფორმაცია შეიძლება გამოყენებულ იქნას გრაფის
სტრუქტურისა და კავშირების შესასწავლად.
უნდობლობის მოდელირების
შესაძლებლობა
წონიანი გრაფებით შესაძლებელია არანამდვილ კავშირების
(ანუ სავარაუდო კავშირების) მოდელირებაც.
მაგალითად, სოციალურ ქსელში წონა შეიძლება ასახავდეს ორ
ადამიანს შორის კავშირის ალბათობას, ნაცვლად იმისა, რომ
გამოვხატოთ მხოლოდ ორობითი დამოკიდებულება — ისინი
„მეგობრები არიან“ ან „არ არიან მეგობრები“.
წონიანი გრაფების ნაკლოვანებები
გაზრდილი სირთულე და ანალიზის გართულება.

მეტი მეხსიერების მოხმარება.

რთული შენარჩუნება (წონის ცვლილებების ეფექტი).

ყველა შემთხვევისთვის არ არის აუცილებელი.

გარკვეული მახასიათებლების მიმართ მიკერძოებულობა.
გაზრდილი სირთულე
წონიანი გრაფები უფრო რთულია შეუწონავი გრაფებისგან
განსხვავებით, რაც მათ ანალიზსა და გაგებას ართულებს.
ეს სირთულე გავლენას ახდენს ისეთი ალგორითმების შექმნაზე,
რომლებიც ამ ტიპის გრაფებზე მუშაობს.
მოიხმარს მეტ მეხსიერებას
ყოველ წიბოზე არსებული წონის გამო, წონიანი გრაფები უფრო
მეტ მეხსიერებას მოითხოვენ.
ეს შეიძლება პრობლემად იქცეს შეზღუდული რესურსების
შემთხვევაში.
რთულია ოპერაციები
წონიანი გრაფების მოდიფიკაცია უფრო რთულია, რადგან
წონის ცვლილება შესაძლოა გავლენას ახდენდეს მთელ გრაფზე.
წიბოების დამატება, წაშლა ან წონის განახლება შეიძლება
რთული პროცესი აღმოჩნდეს.
არ შეესაბამება ყველა ამოცანას
ზოგიერთ ამოცანაში, სადაც კავშირები ბინარულია (არსებობს
ან არ არსებობს), უწონო გრაფი უფრო მარტივი და შესაფერისია
დეიქსტრას ალგორითმი
კლასიკური დეიქსტრას ალგორითმი პოულობს G=(V, E)
ორიენტირებული გრაფისთვის უმოკლეს გზებს საწყისი s
წვეროდან ყველა დანარჩენ წვერომდე. მისი სწორად
მუშაობისთვის აუცილებელია, რომ გრაფის წიბოების წონები
არაუარყოფითი რიცხვები იყოს.
მაგალითი
დეიქსტრას ალგორითმის აღწერა
1. დააინიცირეთ dist[src] = 0, დანარჩენები - უსასრულობა (∞).
2. დაამატეთ src მინ-ჰიპში <0, src>.
3. სანამ მინ-ჰიპი ცარიელი არ არის:
    a. ამოიღეთ ზედა წვერო.

     b. განიხილეთ მისი ყველა მეზობელი.

     c. თუ ახლად გამოთვლილი დისტანცია უკეთესია, განაახლეთ და ჩასვით მინ-
        ჰიპში.
4.    დააბრუნეთ dist მასივი.
ილუსტრაცია
ილუსტრაცია
ილუსტრაცია
ილუსტრაცია
ილუსტრაცია
ილუსტრაცია
ილუსტრაცია
სირთულის შეფასება
დროითი სირთულე: O(E * logV)

დამხმარე მეხსიერება: O(V)
კუნძულების რაოდენობის პოვნა

● მოცემულია n × m ზომის ბადე, რომელშიც არის:
   ○ 'W' — წყალი (Water)
   ○ 'L' — მიწა (Land)
● ამოცანაა, ვიპოვოთ რამდენი ცალკეული კუნძული არსებობს.

კუნძული — ერთმანეთთან ჰორიზონტალურად, ვერტიკალურად ან
დიაგონალურად დაკავშირებული 'L' უჯრების ჯგუფი.
„ბმულობის კომპონენტების რაოდენობის დათვლა არაბმულ
გრაფებში”

სტანდარტული ამოცანის ერთ-ერთი ვარიაცია
მაგალითი
იდეა
იდეა მდგომარეობს იმაში, რომ შევქმნათ დამხმარე მატრიცა,
რომელიც შეინახავს ინფორმაცია იმ წვერების შესახებ,
რომლებიც უკვე მონახულებულია საწყის მატრიცაში, და
შემდეგ გამოვიყენოთ DFS ალგორითმი კუნძულების საერთო
რაოდენობის გამოსათვლელად.
ნაბიჯები
1. დავიწყოთ count = 0-ით და ბულის მნიშვნელობების მქონე მატრიცით
   visited[][], სადაც ყველა მნიშვნელობა საწყისად არის false.

2. გავიაროთ საწყისი მატრიცის ყველა უჯრა და თუ უჯრაში არსებული მნიშვნელობა
   არის L და ეს უჯრა ჯერ არ არის მონახულებული, მაშინ გამოვიძახოთ DFS ამ
   უჯრისა და მისი 8 მეზობელი უჯრისთვის.
         i. თუ მეზობელი უჯრა უსაფრთხოა მოსანახულებლად და ჯერ არ არის
             მონახულებული, რეკურსიულად გამოვიძახოთ DFS და count
             გავზარდოთ 1-ით.

3. საბოლოოდ დავაბრუნოთ count როგორც საბოლოო პასუხი.
სირთულის შეფასება
დროითი სირთულე: O(n* m)

დამხმარე მეხსიერება: O(n* m)
Rotten oranges

მოცემულია m x n განზომილების მატრიცა, რომლის თითოეულ უჯაში შეიძლება იყოს
შემდეგი მნიშვნელობები:

 ●   0: ცარიელი უჯრა
 ●   1: ახალი ფორთოხალი
 ●   2: დამპალი ფორთოხალი

ამოცანაა დადგინდეს მინიმალური დრო, რომლის განმავლობაშიც ყველა ახალი
ფორთოხალი დალპება. ერთი დამპალ ფორთოხალს, რომელიც მდებარეობს ინდექსზე (i,
j), შეუძლია დაალპოს მეზობელი ახალი ფორთოხლები (ზემოთ, ქვემოთ, მარჯვნივ და
მარცხნივ).

შენიშვნა: თუ შეუძლებელია ყველა ფორთოხლის დაძველება, უნდა დავაბრუნოთ -1.
იდეა
იდეა მდგომარეობს იმაში, რომ თითოეული დამპალი ფორთოხლიდან (ანუ 2
მნიშვნელობის უჯრიდან) შესრულდეს DFS (სიღრმისეული ძიება), რათა განვსაზღვროთ
მინიმალური დრო ყველა ახალი ფორთოხლის დასალპობად.
ნაბიჯები
გაიარე მთელი მატრიცა mat[][] — თუ mat[i][j] == 2, ანუ უჯრაში დამპალი
ფორთოხალია, შეასრულე DFS, რათა დაალპო ყველა დაკავშირებული ახალი ფორთოხალი.
DFS-ის ყოველ რეკურსიულ გამოძახებაში შეამოწმე ყველა 4 მიმართულებით დაკავშირებული
უჯრა (ზემოთ, ქვემოთ, მარცხნივ, მარჯვნივ). თუ რომელიმე უჯრაში ახალი ფორთოხალია ან
დაძველებისთვის საჭირო დრო ნაკლებია ვიდრე მანამდე შენახული მნიშვნელობა — გადადი
იმ უჯრაში.
ბოლოს შეამოწმე, დარჩა თუ არა მატრიცაში რომელიმე ახალი ფორთოხალი.

 ●   თუ კი — დაბეჭდე -1
 ●   წინააღმდეგ შემთხვევაში — დაბეჭდე მაქსიმალურად გასული დრო, რაც დაჭირდა ყველა
     ფორთოხლის დასალპობად.
სირთულის შეფასება
დროითი სირთულე: O(n* m)

დამხმარე მეხსიერება: O(1)
იდეა
გამოვყენოთ bfs ალგორითმი ამოცანის ამოსახსნელად
ნაბიჯები
1. შექმენი რიგი (queue), რომელიც შეინახავს ყველა იმ უჯრის კოორდინატს, რომელშიც
   დასაწყისში დამპალი ფორთოხალი (2) მდებარეობს.

2. სანამ რიგი ცარიელი არ არის, გააგრძელე ციკლი. ყოველი იტერაციისას:
     ○ ამოიღე პირველი ელემენტი რიგიდან (შეინახე მის კოორდინატი და გასული დრო),
     ○ შეამოწმე მის გარშემო არსებული ოთხივე მიმართულებით დაკავშირებული უჯრები
         (ზემოთ, ქვემოთ, მარცხნივ, მარჯვნივ),
     ○ თუ რომელიმე მათგანში ახალი ფორთოხალია (1), შეცვალე მისი მდგომარეობა (2),
         დაამატე მისი კოორდინატები რიგში და გაზარდე დრო ერთით.

3. როდესაც რიგი ამოიწურება, შეამოწმე დარჩა თუ არა მატრიცაში ახალი ფორთოხალი:
    ○ თუ კი — დაბეჭდე -1,
    ○ წინააღმდეგ შემთხვევაში — დაბეჭდე მაქსიმალურად გასული დრო.
სირთულის შეფასება
დროითი სირთულე: O(n* m)

დამხმარე მეხსიერება: O(n* m)
გმადლობთ ყურადღებისთვის!
